// https://leetcode.cn/problems/decode-string/

// 算法思路总结：
// 1. 使用双栈处理字符串解码问题
// 2. 数字栈存储重复次数，字符串栈存储待重复片段
// 3. 遇到'['时压入新字符串，遇到']'时弹出并重复
// 4. 处理嵌套编码情况，逐层解码
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <stack>
#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    string decodeString(string s) 
    {
        int m = s.size();

        stack<int> nums;
        stack<string> st;

        st.push("");
        int i = 0;

        while (i < m)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }
            else if (s[i] == '[')
            {
                string tmp;
                i++;
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp);
            }
            else if (s[i] == ']')
            {
                int num = nums.top();
                nums.pop();
                string tmp = st.top();
                st.pop();

                while (num--)
                {
                    st.top() += tmp;
                }
                i++;
            }
            else
            {
                string tmp;
                while (i < m && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.top() += tmp;
            }
        }

        return st.top();
    }
};

int main()
{
    string s1 = "3[a]2[bc]", s2 = "3[a2[c]]";
    Solution sol;

    cout << sol.decodeString(s1) << endl;
    cout << sol.decodeString(s2) << endl;

    return 0;
}